package com.leo.datastruct.tree;

/**
 * 伸展树
 *  http://www.cnblogs.com/skywang12345/p/3604286.html
 * @author xuexiaolei
 * @version 2017年11月30日
 */
public class SplayTree<T extends Comparable<? super T>> {

    private Node<T> mRoot;//根节点

    /**
     * 旋转key对应的节点为根节点，并返回根节点。
     *
     * 注意：
     *   (a)：伸展树中存在"键值为key的节点"。
     *          将"键值为key的节点"旋转为根节点。
     *   (b)：伸展树中不存在"键值为key的节点"，并且key < tree.key。
     *      b-1 "键值为key的节点"的前驱节点存在的话，将"键值为key的节点"的前驱节点旋转为根节点。
     *      b-2 "键值为key的节点"的前驱节点存在的话，则意味着，key比树中任何键值都小，那么此时，将最小节点旋转为根节点。
     *   (c)：伸展树中不存在"键值为key的节点"，并且key > tree.key。
     *      c-1 "键值为key的节点"的后继节点存在的话，将"键值为key的节点"的后继节点旋转为根节点。
     *      c-2 "键值为key的节点"的后继节点不存在的话，则意味着，key比树中任何键值都大，那么此时，将最大节点旋转为根节点。
     *
     * @param tree
     * @param key
     * @return
     */
    private Node<T> splay(Node<T> tree, T key){
        if (tree == null) return  tree;

        Node<T> N = new Node<>();
        Node<T> l = N;
        Node<T> r = N;
        Node<T> c;

        while (true){
            int cmp = key.compareTo(tree.key);
            if(cmp < 0){
                if (tree.left == null) break;

                //右旋    rotate right
                if (key.compareTo(tree.left.key) < 0){
                    c = tree.left;
                    tree.left = c.right;
                    c.right = tree;
                    tree = c;
                    if (tree.left == null) break;
                }
                //右连接   link right
                r.left = tree;
                r = tree;
                tree = tree.left;
            }else if (cmp > 0){
                if (tree.right == null) break;

                //左旋    rotate left
                if (key.compareTo(tree.right.key) > 0) {
                    c = tree.right;
                    tree.right = c.left;
                    c.left = tree;
                    tree = c;
                    if (tree.right == null) break;
                }
                //左连接   link left
                l.right = tree;
                l = tree;
                tree = tree.right;
            }else {
                break;
            }
        }

        l.right = tree.left;
        r.left = tree.right;
        tree.left = N.right;
        tree.right = N.left;

        return tree;
    }

    public void splay(T key){
        mRoot = splay(mRoot, key);
    }

    private Node<T> insert(Node<T> tree, Node<T> z){
        int cmp;
        Node<T> y = null;
        Node<T> x = tree;

        //查找z插入的位置
        while (x!=null){
            y = x;
            cmp = z.key.compareTo(x.key);
            if (cmp < 0){
                x = x.left;
            }else if (cmp > 0){
                x = x.right;
            }else{
                System.out.println("不允许插入相同节点 "+z.key);
                z = null;
                return tree;
            }
        }

        if (y == null){
            tree = z;
        }else {
            cmp = z.key.compareTo(y.key);
            if (cmp < 0){
                y.left = z;
            }else {
                y.right = z;
            }
        }

        return tree;
    }

    public void insert(T key){
        Node<T> z = new Node<>(key, null, null);
        // 插入节点
        mRoot = insert(mRoot, z);
        // 将节点(key)旋转为根节点
        mRoot = splay(mRoot, key);
    }

    /**
     * 删除结点(z)，并返回被删除的结点
     * @param tree 伸展树
     * @param key  z 删除的结点
     * @return
     */
    private Node<T> remove(Node<T> tree, T key){
        Node<T> x;
        if (tree == null) return null;

        // 查找键值为key的节点，找不到的话直接返回
        if (search(tree, key) == null) return null;
        // 将key对应的节点旋转为根节点。
        tree = splay(tree, key);

        if (tree.left != null) {
            // 将"tree的前驱节点"旋转为根节点
            x = splay(tree.left, key);
            // 移除tree节点
            x.right = tree.right;
        }
        else {
            x = tree.right;
        }

        tree = null;

        return x;
    }

    public void remove(T key) {
        mRoot = remove(mRoot, key);
    }

    /**
     * (递归实现)查找"伸展树x"中键值为key的节点
     * @param x
     * @param key
     * @return
     */
    private Node<T> search(Node<T> x, T key) {
        if (x==null) return x;

        int cmp = key.compareTo(x.key);
        if (cmp < 0)
            return search(x.left, key);
        else if (cmp > 0)
            return search(x.right, key);
        else
            return x;
    }

    public Node<T> search(T key) {
        return search(mRoot, key);
    }

    /**
     * 伸展树节点
     * @param <T>
     */
    class Node<T extends Comparable<? super T>>{
        T key;
        Node<T> left;
        Node<T> right;
        Node(){
            this.left = null;
            this.right = null;
        }
        Node(T key, Node<T> left, Node<T> right){
            this.key = key;
            this.right = right;
            this.left = left;
        }
    }
}
